package com.zhanghe.study.suanfa;

/**
 * 贪婪算法  换零钱
 *
 * @author: zhanghe
 * @date: 2020/5/30 22:24
 */
public class Main4 {
    int[] value = {10000, 5000, 2000, 1000, 500, 200, 100, 50, 20, 10, 5, 2, 1};

    public static void main(String[] args) {
        // 面值单位为分  100元、50元、20元、10元、5元、2元、1元、5角、2角、1角、5分、2分、1分
        Main4 m = new Main4();

        m.exchange(1748);

    }

    /**
     * 单位为分
     *
     * @param n
     */
    public void exchange(int n) {
        StringBuilder sb = new StringBuilder();
        int m = 0;
        for (int i = 0; i < value.length; i++) {
            if (n < value[i]) {
                continue;
            }
            m = n / value[i];
            n = n - m * value[i];
            if (value[i] > 100) {
                sb.append(m).append("张").append(value[i] / 100).append("元,");
            } else if (value[i] > 10) {
                sb.append(m).append("张").append(value[i] / 10).append("角,");
            } else {
                sb.append(m).append("张").append(value[i]).append("分,");
            }
        }
        if (sb.indexOf(",") > 0 && sb.lastIndexOf(",") == sb.length() - 1) {
            sb.deleteCharAt(sb.length() - 1);
        }
        System.out.println(sb.toString());
    }
}
